The present invention relates to systems and methods for scheduling resources such as, e.g., packet transmission resources.
High speed networks are designed to carry services with a wide range of traffic characteristics and quality-of-service (QoS) requirements. A common task for rate-based QoS enabled scheduling is ensuring that each of multiple queues is guaranteed a minimum rate, excess bandwidth is shared in accordance with predefined weights, each queue does not exceed a specified maximum rate, and the link is maximally utilized within the maximum rate constraints.
It is further desirable to extend rate-based scheduling to a class hierarchy where the above-described rates are configured in a hierarchical fashion. Such a class hierarchy may be represented as a tree of nodes. The root node would then correspond to the physical interface, nodes of the next layer would correspond to a logical interface, and a third layer might correspond to particular client. Each node is expected to be served by its parent node at least at its configured minimum service rate and up to its maximum configured rate. The excess service that can be given to a node above and beyond its minimum rate is desirably proportional to its specified excess bandwidth sharing weight relative to the weights of its active non-empty peers that are simultaneously vying for excess service.
One known way to schedule in accordance with class hierarchy requirements is to employ essentially two scheduling systems, a minimum rate scheduler and an excess weight scheduler. Each node has an associated queue. For the leaf nodes of the tree, the queues are actual packet queues. For higher layer nodes, the queues are logical queues. The minimum rate scheduler only considers queues that are not exceeding their minimum rates. The excess rate scheduler considers ones of the remaining queues that are not exceeding their maximum rates. At each scheduling opportunity, the minimum rate scheduler is invoked if it has a non-empty queue to schedule; otherwise a queue is selected by the maximum rate scheduler.
A problem with this approach is that, due to the passage of time, many queues may return simultaneously, or nearly simultaneously, to eligibility for consideration by the minimum rate scheduler. Correctly returning newly eligible queues to the minimum rate scheduler, however, requires O(N) complexity where N is the number of returning queues.
The above-cited application entitled “Scheduling System and Method for Multi-Level Class Hierarchy” solves this problem by providing that ineligible queues remain in consideration by the minimum rate scheduler. When the minimum rate scheduler selects an ineligible queue, its token bucket is updated and its eligibility is reconsidered. However, if it remains ineligible, the scheduling opportunity is given to the maximum rate scheduler which only considers queues that currently exceed their configured minimum rates. In this way, each ineligible queue is guaranteed to have its eligibility considered at least every 1/R time units.
A shortcoming of the approach described in the cited patent application is that it delivers service in a bursty fashion in some scenarios. Underlying the two schedulers are respective calendar queues operative at each parent node in the hierarchy. The calendar queues provide an efficient implementation structure, but have some intrinsic inaccuracy in their scheduling among the queues of children nodes. The inaccuracy may result in a late return to eligibility for a node queue that has in fact already fallen below its minimal rate. Once the calendar queue gets around to returning this queue to eligibility, its packets will tend to be serviced consecutively to balance out the previous underservicing. The result is bursts of traffic from the various queues and poor rate control over short periods of time.
What is needed are systems and methods for operating a two-rate scheduler such that rate control is delivered in a smooth manner and rates remain controlled even over relatively short time intervals.